<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
</head>

<body>
    <div id="app"></div>
    <script>
        // 创建虚拟DOM节点（VNode）的函数
        function createVNode(tag, props = {}, children) {
            return {
                tag,
                props,
                children,
                key: props.key || null,
                el: null
            };
        }

        // 判断两个VNode是否为相同类型节点（依据标签和key判断）
        function isSameVNodeType(n1, n2) {
            return n1.tag === n2.tag && n1.key === n2.key;
        }

        // 挂载单个VNode到指定容器中
        function mountVNode(vnode, container, anchor = null) {
            const el = vnode.el = document.createElement(vnode.tag);
            // 设置属性
            for (const key in vnode.props) {
                if (key === 'class') {
                    el.className = vnode.props[key];
                } else if (key === 'style') {
                    const styleObj = vnode.props[key];
                    for (const styleKey in styleObj) {
                        el.style[styleKey] = styleObj[styleKey];
                    }
                } else {
                    el.setAttribute(key, vnode.props[key]);
                }
            }
            // 处理子节点
            if (Array.isArray(vnode.children)) {
                vnode.children.forEach(child => {
                    mountVNode(child, el);
                });
            } else if (vnode.children != null) {
                el.textContent = vnode.children;
            }
            // 将元素插入容器中
            if (anchor) {
                container.insertBefore(el, anchor);
            } else {
                container.appendChild(el);
            }
            return el;
        }

        // 卸载VNode对应的真实DOM元素
        function unmountVNode(vnode) {
            if (vnode.el && vnode.el.parentNode) {
                vnode.el.parentNode.removeChild(vnode.el);
            }
        }

        // 对比更新节点属性
        function patchProps(oldProps, newProps, el) {
            // 移除旧属性中不存在于新属性中的属性
            for (const key in oldProps) {
                if (!(key in newProps)) {
                    el.removeAttribute(key);
                }
            }
            // 更新或添加新属性
            for (const key in newProps) {
                if (oldProps[key] !== newProps[key]) {
                    if (key === 'class') {
                        el.className = newProps[key];
                    } else if (key === 'style') {
                        const styleObj = newProps[key];
                        for (const styleKey in styleObj) {
                            el.style[styleKey] = styleObj[styleKey];
                        }
                    } else {
                        el.setAttribute(key, newProps[key]);
                    }
                }
            }
        }

        // 移动节点到新的位置
        function moveVNode(vnode, container, anchor) {
            const el = vnode.el;
            if (anchor) {
                container.insertBefore(el, anchor);
            } else {
                container.appendChild(el);
            }
        }

        // 对比更新子节点（核心的diff逻辑所在，处理新旧子节点的各种情况）
        function patchChildren(n1, n2, container) {
            const c1 = n1.children;
            const c2 = n2.children;
            const prevShapeFlag = n1.shapeFlag;
            const shapeFlag = n2.shapeFlag;

            if (shapeFlag & 8 /* ShapeFlag.ARRAY_CHILDREN */) {
                if (prevShapeFlag & 8 /* ShapeFlag.ARRAY_CHILDREN */) {
                    patchKeyedChildren(c1, c2, container);
                } else {
                    // 旧子节点不是数组，新子节点是数组，先卸载旧子节点，再挂载新子节点
                    if (c1) {
                        unmountVNode(c1);
                    }
                    mountChildren(c2, container);
                }
            } else {
                if (prevShapeFlag & 8 /* ShapeFlag.ARRAY_CHILDREN */) {
                    // 旧子节点是数组，新子节点不是数组，卸载旧子节点
                    if (c1) {
                        unmountVNode(c1);
                    }
                } else {
                    // 新旧子节点都不是数组，对比更新文本节点或其他单个子节点情况
                    if (c1 !== c2) {
                        if (c1) {
                            n1.el.textContent = c2;
                        } else {
                            const el = document.createElement(n2.tag);
                            el.textContent = c2;
                            container.appendChild(el);
                        }
                    }
                }
            }
        }

        // 对比更新有key的子节点数组（核心diff算法中处理列表等场景的关键逻辑）
        function patchKeyedChildren(c1, c2, container) {
            const oldLen = c1.length;
            const newLen = c2.length;
            const keyToNewIndexMap = new Map();
            const newIndexToOldIndexMap = new Array(newLen).fill(-1);
            let lastIndex = 0;

            // 第一步：构建新节点的key到索引的映射，以及初始化新索引到旧索引的映射
            for (let i = 0; i < newLen; i++) {
                const nextChild = c2[i];
                keyToNewIndexMap.set(nextChild.key, i);
            }

            // 第二步：遍历旧子节点，根据key查找在新节点中的位置，标记新旧索引映射，处理未找到的旧节点（删除）
            for (let i = 0; i < oldLen; i++) {
                const prevChild = c1[i];
                const newIndex = keyToNewIndexMap.get(prevChild.key);
                if (newIndex === undefined) {
                    // 旧节点在新节点中不存在，卸载该旧节点
                    unmountVNode(prevChild);
                } else {
                    newIndexToOldIndexMap[newIndex] = i;
                    const nextChild = c2[newIndex];
                    if (isSameVNodeType(prevChild, nextChild)) {
                        // 节点类型相同，进行更新
                        patch(prevChild, nextChild, prevChild.el.parentNode);
                    } else {
                        // 节点类型不同，先卸载旧节点，再挂载新节点
                        unmountVNode(prevChild);
                        mountVNode(nextChild, container);
                    }
                    if (newIndex < lastIndex) {
                        // 节点需要移动位置，移动到正确的位置
                        const anchor = newIndex + 1 < newLen ? c2[newIndex + 1].el : null;
                        moveVNode(nextChild, container, anchor);
                    } else {
                        lastIndex = newIndex;
                    }
                }
            }

            // 第三步：处理新增节点（在新节点中存在但旧节点中没有的），进行挂载
            for (let i = 0; i < newLen; i++) {
                const oldIndex = newIndexToOldIndexMap[i];
                if (oldIndex === -1) {
                    const nextChild = c2[i];
                    const anchor = i < newLen - 1 ? c2[i + 1].el : null;
                    mountVNode(nextChild, container, anchor);
                }
            }
        }

        // 挂载多个子节点到容器中
        function mountChildren(children, container) {
            children.forEach(child => {
                mountVNode(child, container);
            });
        }

        // 对比更新两个VNode（整体入口函数）
        function patch(n1, n2, container) {
            if (n1 === n2) {
                return;
            }
            if (!n1) {
                mountVNode(n2, container);
            } else if (!n2) {
                unmountVNode(n1);
            } else if (isSameVNodeType(n1, n2)) {
                const el = n1.el;
                patchProps(n1.props, n2.props, el);
                patchChildren(n1, n2, el);
            } else {
                unmountVNode(n1);
                mountVNode(n2, container);
            }
        }

        // 示例用法，创建一些虚拟DOM节点并进行对比更新操作
        let oldVNodes = createVNode('ul', {}, [
            createVNode('li', { key: 'a' }, 'a'),
            createVNode('li', { key: 'b' }, 'b'),

            createVNode('li', { key: 'c' }, 'c'),
            createVNode('li', { key: 'd' }, 'd'),
            createVNode('li', { key: 'e' }, 'e'),

            createVNode('li', { key: 'f' }, 'f'),
            createVNode('li', { key: 'g' }, 'g'),
        ])

        let newVNodes = createVNode('ul', {}, [
            createVNode('li', { key: 'a' }, 'a'),
            createVNode('li', { key: 'b' }, 'b'),

            createVNode('li', { key: 'e' }, 'e'),
            createVNode('li', { key: 'd' }, 'd'),
            createVNode('li', { key: 'c' }, 'c'),
            createVNode('li', { key: 'h' }, 'h'),

            createVNode('li', { key: 'f' }, 'f'),
            createVNode('li', { key: 'g' }, 'g'),
        ])


        const app = document.getElementById('app');
        patch(null, oldVNodes, app);
        patch(oldVNodes, newVNodes, app);

    </script>
</body>

</html>